/**
 * dict.c
 * 内存字典的一种通俗实现。
 * 
 * 2022.02 */
#include "dict.h"

#define DICT_FREE(d) ({if (d->flag & DICT_FLAG_FREE) d->app.mfree(d);})

static int 
_dictHtblSet(DICT_S *d, DICT_HTBL_S *ht, size_t size)
{
    size_t i;
    DICT_HNODE_S **en = NULL;

    if (0 != size) {
        en = (DICT_HNODE_S **) d->app.malloc(sizeof(DICT_HNODE_S *) * size);
        if (NULL == en) return COM;
    }

    for (i = 0; i < size; ++i) en[i] = NULL;
    ht->en  = en, ht->ens = size;
    ht->nds = 0;
    return COK;
}

static void 
_dictUpgradeDone(DICT_S *d)
{
    DICT_HTBL_S *ht = d->ht;

    d->app.mfree(ht[0].en);
    d->ui = 0, d->vers += 1;

    ht[0] = ht[1];
    (void) _dictHtblSet(d, ht+1, 0);
    return ;
}

static int 
_dictUpgrade(DICT_S *d, size_t up_nmax)
{
    size_t up = 0;
    DICT_HTBL_S *ht = d->ht;
    DICT_APP_S  *a = &d->app;
    size_t i, ens = ht[0].ens;

    for (i = d->ui; i < ens; ++i) {
        DICT_HNODE_S **p = &ht[0].en[i];
        DICT_HNODE_S *c = *p, **h;
        uint64_t e;

        while (c) {
            e = a->khash(&c->item.k) % ht[1].ens;
            h = &ht[1].en[e];

            *p = c->next;
            c->next = *h, *h = c;
            ht[0].nds -= 1;
            ht[1].nds += 1;

            c = *p;
            up += 1;
        }
        if (++up > up_nmax) goto _upgrade;
    }

_upgrade:
    if (i == ens) {
        _dictUpgradeDone(d);
        return CDONE;
    }
    d->ui = i;
    return CING;
}

/**
 * 升级；
 * 扩容升级；
 * 缩容升级；
 * 字典容量尚融洽时什么也不做。*/
static int 
_dictUpgradeChk(DICT_S *d)
{
    int ret;
    size_t size;
    DICT_APP_S *a = &d->app;
    DICT_HTBL_S *ht = d->ht;

    if (0 != ht[1].ens) {
        return _dictUpgrade(d, a->up_nmax);
    }

    if (ht[0].nds / ht[0].ens >= a->up_ratio) {
        size = CMIN((ht[0].ens << 1) + 1, a->size_max);
        ret  = _dictHtblSet(d, ht+1, size);
        if (COK != ret) return ret;
        return _dictUpgrade(d, a->up_nmax);
    }

    if (ht[0].ens > a->size_min && ht[0].nds * a->up_ratio < ht[0].ens) {
        size = ht[0].nds * a->up_ratio + a->size_min;
        ret  = _dictHtblSet(d, ht+1, size);
        if (COK != ret) return ret;
        return _dictUpgrade(d, a->up_nmax);
    }

    return CDONE;
}

static DICT_HNODE_S *
_dictFind(DICT_S *d, const COMM_DATA_U *k, DICT_HTBL_S **ht, DICT_HNODE_S ***prev)
{
    size_t i, e;
    DICT_HNODE_S **p, *c;
    DICT_HTBL_S *v = NULL;
    DICT_HTBL_S *t = d->ht;
    DICT_APP_S  *a = &d->app;

    (void) _dictUpgradeChk(d);
    for (i = 0; i < DICT_VERS; ++i) {
        if (0 == t[i].ens) continue;

        v = t + i;
        e = a->khash(k) % t[i].ens;
        p = &t[i].en[e], c = *p;
        for (/**/; c; p = &c->next, c = c->next) {
            if (0 == a->kcmp(&c->item.k, k))
                goto _find;
        }
    }

_find:
    if (ht) *ht = v;
    if (prev) *prev = p;
    return c;
}

DICT_S * dictAppoint(DICT_S *d, const DICT_APP_S *app)
{
    DICT_S *_d = d;
    void *(*_malloc)(size_t) = app->malloc ? app->malloc : malloc;

    if (NULL == _d) {
        if (NULL == (_d = (DICT_S *) _malloc(sizeof(*_d)))) return NULL;
        _d->flag = DICT_FLAG_FREE;
    } else {
        _d->flag = 0;
    }

    DICT_APP_S *a = &_d->app;
    a->khash = app->khash;
    a->irset = app->irset;
    a->kcmp  = app->kcmp;
    a->uext  = app->uext;
    a->malloc = _malloc;
    a->mfree  = app->mfree ? app->mfree : free;
    a->size_min = CMIN(app->size_min, DICT_SIZE_MIN);
    a->size_max = CMAX(app->size_max, DICT_SIZE_MIN);
    a->up_nmax  = CMAX(app->up_nmax,  DICT_SIZE_MIN);
    a->up_ratio = CMAX(app->up_ratio, DICT_RATIO_MIN);

    int ret;
    d->ui = d->vers = 0;
    (void) _dictHtblSet(_d, &_d->ht[1], 0);
    ret =  _dictHtblSet(_d, &_d->ht[0], a->size_min);
    if (COK != ret) {
        DICT_FREE(_d);
        return NULL;
    }
    return _d;
}

COMM_DATA_U * dictAdd(DICT_S *d, DICT_HNODE_S *n, int *exist)
{
    DICT_HTBL_S  *ht;
    DICT_HNODE_S *f;
    DICT_HNODE_S **prev;

    f = _dictFind(d, &n->item.k, &ht, &prev);
    if (NULL != f) {
        if (NULL != exist) *exist = DICT_ITEM_EXIST;
        return &f->item.v;
    }

    n->next = *prev, *prev = n;
    ht->nds += 1;
    return &n->item.v;
}

COMM_DATA_U * dictFind(DICT_S *d, const COMM_DATA_U *k)
{
    DICT_HNODE_S *f;

    f = _dictFind(d, k, NULL, NULL);
    return f ? &f->item.v : NULL;
}

int dictDel(DICT_S *d, const COMM_DATA_U *k)
{
    DICT_HTBL_S   *ht;
    DICT_HNODE_S  *del;
    DICT_HNODE_S **prev;

    del = _dictFind(d, k, &ht, &prev);
    if (NULL == del) return COK;

    DICT_APP_S   *a = &d->app;
    DICT_HNODE_S *next = del->next;
    int ret = a->irset(del, a->uext);
    if (COK != ret) return ret;

    *prev = next;
    ht->nds -= 1;
    return COK;
}

int dictUpgrade(DICT_S *d, uint64_t up_tmax)
{
    int ret;
    uint64_t now;
    uint64_t start = comm_getnsec();

    do {
        ret = _dictUpgradeChk(d);
        if (ret == CDONE || CING != ret)
            break;
        now = comm_getnsec();
    } while (now - start < up_tmax);
    return ret;
}

int dictRemove(DICT_S *d)
{
    int i, e;
    DICT_HTBL_S *t = d->ht;
    DICT_APP_S  *a = &d->app;
    DICT_HNODE_S **p, *c, *n;

    for (i = 0; i < DICT_VERS; ++i) {
        for (e = 0; e < t[i].ens; ++e) {
            int ret;
            p = &t[i].en[e], c = *p;
            for (/**/; c; *p = c = n) {
                n = c->next;
                ret = a->irset(c, a->uext);
                if (COK != ret) return ret;
            }
        }
        a->mfree(t[i].en);
        _dictHtblSet(d, t+i, 0);
    }
    d->vers = d->ui = 0;
    DICT_FREE(d);
    return COK;
}

//#define DICT_TEST
#ifdef DICT_TEST
static uint64_t tkhash(const COMM_DATA_U *k)
{
    return (uint64_t)k->s64;
}

static int tkcmp(const COMM_DATA_U *dk, const COMM_DATA_U *uk)
{
    return !(dk->s64 == uk->s64);
}
static int tirset(DICT_HNODE_S *n, const void *uext)
{
    (void)uext;
    (void)n;
    return COK;
}

#include <assert.h>
int main(void)
{
    DICT_S d;
    DICT_APP_S app = {
        .khash = tkhash,
        .kcmp  = tkcmp,
        .malloc = NULL,
        .mfree  = NULL,
        .irset  = tirset,
        .uext   = NULL,
        .size_min = DICT_SIZE_MIN,
        .size_max = (1<<20) + 1,
        .up_nmax  = DICT_SIZE_MIN,
        .up_ratio = 8,
    };

    assert(NULL != dictAppoint(&d, &app));
    fprintf(stderr,
            "%d"
            " ui %u"
            " vers %u"
            " ens %u %u"
            " nds %u %u\n",
            __LINE__, d.ui, 
            d.vers,
            d.ht[0].ens, d.ht[1].ens,
            d.ht[0].nds, d.ht[1].nds);

#define DICT_SIZE (1<<20)
    DICT_HNODE_S *hn = (DICT_HNODE_S *)malloc(sizeof(DICT_HNODE_S) * DICT_SIZE);
    assert(NULL != hn);

    int i;
    int exist;
    for (i = 0; i < DICT_SIZE; ++i) {
        hn[i].item.k.s64 = i;
        hn[i].item.v.s64 = i;

        exist = 0;
        dictAdd(&d, hn + i, &exist);
        assert(DICT_ITEM_EXIST != exist);
    }
    fprintf(stderr,
            "%d"
            " ui %u"
            " vers %u"
            " ens %u %u"
            " nds %u %u\n",
            __LINE__, d.ui, 
            d.vers,
            d.ht[0].ens, d.ht[1].ens,
            d.ht[0].nds, d.ht[1].nds);

#define DICT_FIND_RAND  (DICT_SIZE >> 1)
    srand(time(NULL) ^ DICT_FIND_RAND);
    for (i = 0; i < DICT_FIND_RAND; ++i) {

        int k = rand() % DICT_SIZE;
        exist = 0;
        dictAdd(&d, hn + k, &exist);
        assert(DICT_ITEM_EXIST == exist);

        COMM_DATA_U uk;
        uk.s64 = k;
        COMM_DATA_U *v = dictFind(&d, &uk);
        assert(v != NULL && v->s64 == k);
    }
fprintf(stderr,
            "%d"
            " ui %u"
            " vers %u"
            " ens %u %u"
            " nds %u %u\n",
            __LINE__, d.ui, 
            d.vers,
            d.ht[0].ens, d.ht[1].ens,
            d.ht[0].nds, d.ht[1].nds);
    while (CING == dictUpgrade(&d, 100000000)) {;}
fprintf(stderr,
            "%d"
            " ui %u"
            " vers %u"
            " ens %u %u"
            " nds %u %u\n",
            __LINE__, d.ui, 
            d.vers,
            d.ht[0].ens, d.ht[1].ens,
            d.ht[0].nds, d.ht[1].nds);

    for (i = 0; i < DICT_SIZE; ++i) {
        COMM_DATA_U uk;
        uk.s64 = i;

        int ret = dictDel(&d, &uk);
        assert(COK == ret);
    }
    while (CING == dictUpgrade(&d, 100000000)) {;}
fprintf(stderr,
            "%d"
            " ui %u"
            " vers %u"
            " ens %u %u"
            " nds %u %u\n",
            __LINE__, d.ui, 
            d.vers,
            d.ht[0].ens, d.ht[1].ens,
            d.ht[0].nds, d.ht[1].nds);
    assert(COK == dictRemove(&d));
    free(hn);
    getchar();
}
#endif